package lhc.alg.top100;

import java.util.PriorityQueue;

/**
 * description: https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
 *  最小的k个数
 *
 *  解法： 直接用堆把  直接sort排序会遭人耻笑
 *
 * author: hongchen.liao
 * date:  2022/7/22
 */
public class _InterviewTopic_40_smallest_number_of_k {

    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            int[] res = new int[k];
            if(k == 0){
                return res;
            }
            PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->(b-a));
            for(int i = 0; i < k; i++){
                pq.offer(arr[i]);
            }
            for(int i = k; i < arr.length; i++){
                if(pq.peek() > arr[i]){
                    pq.poll();
                    pq.offer(arr[i]);
                }
            }
            for(int i = 0; i < k; i++){
                res[i] = pq.poll();
            }
            return res;

        }
    }


}
